package xyz.scootaloo.oj.offer

import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/9 14:06
 */
class P14I {

    /**
     * 1,  2,  3,  4,  5,  6, 7
     *
     * 1   1   1   2   2   3  3
     *     1   2   2   3   3  4
     */
    private fun cuttingRope(n: Int): Int {
        if (n == 0) return 0
        if (n <= 2) return 1
        if (n == 3) return 2
        val dp = IntArray(n + 1)
        dp[1] = 1
        dp[2] = 1
        for (idx in 2..n) {
            var currentMax = idx
            for (pos in 2..(idx / 2)) {
                currentMax = max(currentMax, pos * max(idx - pos, dp[idx - pos]))
            }
            dp[idx] = currentMax
        }

        return dp[n]
    }

    private fun max(a: Int, b: Int): Int = if (a > b) a else b


    @Test
    fun test0() {
        println(cuttingRope(1))
        println(cuttingRope(2))
        println(cuttingRope(3))
        println(cuttingRope(4))
        println(cuttingRope(10))
    }

}
